/**
 * @author LKQ
 * @date 2021/12/10 16:32
 * @description 时间复杂度O(n^2) ，超出时间限制，无法ac
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] prices = {7,1,5,3,6,4};
        solution.maxProfit(prices);
    }

    public int maxProfit(int[] prices) {
        int max = 0, n = prices.length;
        int[] maxProfit = new int[n];
        for (int i = 0; i < n; i++) {
            int temp = prices[i];
            for (int j = i; j < n; j++) {
                int profit =  prices[j] - temp;
                if ( profit > maxProfit[j]) {
                    maxProfit[j] = profit;
                }
            }
        }
        for(int i : maxProfit) {
            if (max <= i) {
                max = i;
            }
        }
        return max;
    }
}
